Принцип включений-исключений

Пусть $A$ — конечное множество, $A_1, \ldots, A_k$ — его подмножества (не обязательно различные). Тогда $$ \left|\bigcup_{i=1}^{k} A_i\right| = \sum_{\substack{X \neq \varnothing \\ X \subseteq \{1, \dots, k\}}} (-1)^{|X|-1} \left|\bigcap_{i \in X} A_i\right|. \quad (1) $$

Возьмем произвольный элемент $a \in \bigcup_{i=1}^{k} A_i$. Пусть $Z = \{i \mid a \in A_i\}$ — множество индексов тех подмножеств, которым принадлежит $a$. Элемент $a$ входит во множество в левой части (1), т.е. добавляет к ней 1. В правой части (1) элемент $a$ входит во множество $\bigcap_{i \in X} A_i$ тогда и только тогда, когда $X \subseteq Z$. Для каждого такого $X$ он добавляет 1 к $\left|\bigcap_{i \in X} A_i\right|$. Следовательно, вклад элемента $a$ в правую часть равен: $$C_a = \sum_{\substack{X \subseteq Z \\ X \neq \varnothing}} (-1)^{|X|-1} \cdot 1$$ Пусть $m = |Z|$. Сгруппируем в формуле для $C_a$ множества равной мощности $j = |X|$: $$C_a = \sum_{j=1}^{m} \binom{m}{j} (-1)^{j-1} = \left(\sum_{j=0}^{m} \binom{m}{j} (-1)^{j-1}\right) - \binom{m}{0}(-1)^{-1} = -\sum_{j=0}^{m} \binom{m}{j} (-1)^{j} + 1 = -(1-1)^m + 1 = 1$$ Итак, каждый элемент добавляет 1 к левой и 1 к правой части (1). Следовательно, левая и правая части (1) равны. $\square$

Перепишем формулу (1) в виде: $$|\bigcup_{i=1}^{k} A_i| = \sum_{j=1}^{k} (-1)^{j-1} \left(\sum_{\substack{X \subset [ 1..k] \\ |X|=j}} |\bigcap_{i \in X} A_i|\right)$$ Пусть для $j = 1, \dots, k$: $$N_j = \left(\sum_{\substack{X \subset [ 1..k] \\ |X|=j}} |\bigcap_{i \in X} A_i|\right); \text{ доопределим } N_0 = |A|$$ Тогда число элементов, не обладающих ни одним из $k$ свойств, есть: $$|A \setminus \bigcup_{i=1}^{k} A_i| = |A| - |\bigcup_{i=1}^{k} A_i| = N_0 - \sum_{j=1}^{k} (-1)^{j-1} N_j = N_0 + \sum_{j=1}^{k} (-1)^{j} N_j = \sum_{j=0}^{k} (-1)^{j} N_j$$

Пусть $|\bigcap_{i \in X} A_i| = s_{|X|}$ зависит только от $|X|$; тогда: $$N_j = \binom{k}{j} s_j$$